package com.dyz.swordFingerOffer;

import java.util.Stack;

/**
 * @author: daiyizheng
 * @date: 2021/5/30 20:46
 * @description:
 */
public class ReverseList24 {
    public ListNode ReverseList(ListNode head) {
        if(head==null){return null;}
        ListNode dummy = new ListNode(0);
        ListNode body = head;
        ListNode cur = head.next;
        while(cur!=null){
            body.next = dummy.next;
            dummy.next = body;
            body = cur;
            cur = cur.next;
        }
        if(body!=null){//body 最后一个位置
            body.next = dummy.next;
            dummy.next = body;
        }
        return dummy.next;
    }

    public ListNode reverseList1(ListNode head) {
        if(head == null || head.next == null) {return head;}
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        //入栈
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        //建立虚拟头节点，构建新的链表
        ListNode dummy = new ListNode(0);
        cur = dummy;
        while(!stack.isEmpty()){
            cur.next = stack.pop();
            cur = cur.next;
        }
        //注意这一句不能少，否则最后两个节点会形成环，
        //如题中反转后2的下一个节点是1，而原链表1的下一个节点是2
        //如果没有下面这行代码，2的下一个节点是1，1的下一节点是2，而不是null，形成环了
        cur.next = null;
        return dummy.next;
    }
}
